package 力扣链表;

public class Leedcode92反转链表 {

    public static void main(String[] args) {
//        ListNode node5 = new ListNode(5,null);
//        ListNode node4 = new ListNode(4,node5);
//        ListNode node3 = new ListNode(3,node4);
        ListNode node2 = new ListNode(2,null);
        ListNode node1 = new ListNode(1,node2);
        Leedcode92反转链表 obj = new Leedcode92反转链表();
        obj.reverseBetween(node1,1,2);
    }

    ListNode successor;
    public ListNode reverseBetween(ListNode head, int left, int right) {
        if (left == 1){
            return reverseN(head,right);
        }
        head.next = reverseBetween(head.next,left-1,right-1);
        return head;
    }
    //反转前N个节点
    public ListNode reverseN(ListNode head,int n) {
        //如果n==1,则说明就反转一个节点，就等于不反转
        if (n == 1){
            successor = head.next;
            return head;
        }
        //n > 2
        ListNode temp = head.next;
        ListNode newHead = reverseN(head.next,n-1);
        temp.next = head;
        head.next = successor;
        return newHead;
    }



    /**
     * 给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。
     * 就反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。
     *
     * 链表中节点数目为 n
     * 1 <= n <= 500
     * -500 <= Node.val <= 500
     * 1 <= left <= right <= n
     *
     * @param head
     * @param left
     * @param right
     * @return
     */
    public ListNode reverseBetween1(ListNode head, int left, int right) {
        //递归终止条件,如果head.next == null，直接返回
        if (head.next == null){
            return head;
        }
        ListNode cur = new ListNode();
        cur.next = head;
        ListNode before = cur;
        //否则找到需要   反转的节点的  前驱节点before;  假如left = 2，i = 0，i
        for (int i = 0; i < left - 1; i++) {
            before = before.next;
        }
        //找反转节点的开始节点
        ListNode leftNode = before.next;
        //然后将before指向空，避免环状链表。
        before.next = null;
        //找到需要反转的节点的末节点
        ListNode cur1 = new ListNode();
        cur1 = leftNode;
        for (int i = 0; i < right - left; i++) {
            cur1 = cur1.next;
        }
        ListNode end = new ListNode();

        //找到反转链表的尾节点
        ListNode rightNode = cur1;
        //记录要反转链表  尾节点的下一个节点end；
        end = rightNode.next;
        //将rightNode.next 质控，避免环形链表
        rightNode.next = null;


        //然后反转需要反转的部分链表
        ListNode reverseList = reverseList(leftNode);
        // 然后拼接前一半
        before.next = reverseList;

        //拼接后一半,后一半的节点的尾节点现在经过反转，leftNode成了reverseList的为节点
        leftNode.next = end;

        //     //返回结果
        return cur.next;
    }
    public ListNode reverseList(ListNode head) {
        //1递归终止条件
        if (head == null || head.next == null) {
            return head;
        }
        //保存第二个节点的地址
        ListNode temp = head.next;
        //将第二节点以后反转，得到新头节点
        ListNode node = reverseList(head.next);
        //让第二个节点的next指向head
        temp.next = head;
        //消除环
        head.next = null;
        //2得到剩余节点逆转后的链表，
        return node;
    }
}
